/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(n, dislikes) {
  // 标记，0为未访问，1,2分别为两个阵营
  let node = new Array(n).fill(0);
  let record = new Array(n);

  // 一开始就设置为true，表示默认为成功的场景
  // 这样我们只需要考虑false，失败的场景就可以了
  let flag = true;

  /**
   * @param {传过来的节点索引值} index
   * @param {传过来的阵营值：1或2} value
   * @returns
   */
  function dfs(index, value) {
    // 设置阵营
    node[index] = value;
    // 相反的阵营
    let antiValue = value == 1 ? 2 : 1;
    for(let i = 0; i < record[index].length; i++) {
      if(node[record[index][i]] === 0) {
        // 如果没有访问过,将该节点的索引进行深搜递归，将值设置为与index相反的阵营
        dfs(record[index][i], antiValue);
        // 如果最后深搜完了之后，发现flag为false了，就没有必要进行下去了
        if(!flag) return ;
      } else if(node[record[index][i]] == node[index]) {
        // 如果该节点被访问过了，而且所处的阵营与index一样，那么就失败了，两个不喜欢的人在一起了
        flag = false;
        return ;
      }
    }
  }

  for(let i = 0; i < record.length; i++) {
    record[i] = [];
  }
  for(let i = 0; i < dislikes.length; i++) {
    // 这里因为节点为1开始，因此我们让所有节点减1就可以直接用数组处理了
    // 例如：原来的节点1, 2, 3, 4, 5
    // 变为:0, 1, 2, 3, 4
    dislikes[i][0] -= 1, dislikes[i][1] -= 1;
    record[dislikes[i][0]].push(dislikes[i][1]);
    record[dislikes[i][1]].push(dislikes[i][0]);
  }
  for(let i = 0; i < n && flag; i++) {
    if(node[i] == 0) {
      dfs(i, 1);
    }
  }
  return flag;
};
let n = 4, dislikes = [[1,2],[1,3],[2,4]];
console.log(possibleBipartition(n, dislikes));
n = 3, dislikes = [[1,2],[1,3],[2,3]];
console.log(possibleBipartition(n, dislikes));
n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]];
console.log(possibleBipartition(n, dislikes));
